1. Field of the Invention
The present invention relates generally to transformation of digital images in computer graphics systems and, more particularly, to an interpolation method and apparatus for performing fast and accurate image transformations.
2. Related Art
A digital image of an object is formed as an array of rows and columns of pixels, which correspond to pixels on a display screen or other display device. Pixels are typically identified by their x, y coordinates in the pixel array. Each pixel has one or more associated values which represent an incremental area of the object. When the image is a black and white image, the pixel value represents a gray shade of the incremental area. When the image is a color image, red, green and blue (R,G,B) values are associated with each pixel. Examples of digital images include, but are not limited to, medical images such as digital x-rays and MRI images, digital film images, digital video images, and satellite images.
Various spatial transformations may be performed on a digital image. These transformations include scaling, rotation and translation of an image or a portion of an image. When an image of an object is magnified, a resampling is required to map the original, or source, image to a magnified, or destination, image. The magnified image is represented by a greater number of pixels than the source image.
A conventional technique for magnifying an image of an object involves a reverse mapping of pixels from the magnified image to resampled points in the source image. In general, the resampled points in the source image do not coincide exactly with single pixel locations. Accordingly, it is necessary to determine a pixel value of the resampled point from one or more pixel values in the neighborhood of the resampled point. Which neighbor pixels of the resampled point are selected depends upon the approach used to determine the value of the resampled point. In one approach, the value of the resampled point is determined as the value of the nearest neighbor pixel in the source image. In another approach, interpolation between a selected number of neighbor pixels is used to determine the value of the resampled point. Typically, either bilinear or bicubic interpolation is utilized. In bilinear interpolation, the four nearest neighbor pixels of the resampled point are determined. Vertically-aligned intermediate pixel values are determined by interpolation between sets of two horizontally-aligned neighbor pixels. Then, the pixel value of the resampled point is determined by interpolation between the vertically-aligned intermediate pixel values. This procedure is repeated for each pixel in the magnified image.
A similar approach is used for bicubic interpolation. There, the sixteen nearest neighbor pixels of the resampled point are determined. Vertically-aligned intermediate pixel values are determined by interpolating between sets of four horizontally-aligned neighbor pixels. Then, the pixel value of the resampled point is determined by interpolation between the four vertically-aligned intermediate pixel values. The process is also repeated for each pixel in the magnified image.
A typical magnified image may have 400.times.400 to 1600.times.1200 pixels. The interpolation operations, which require multiple computations for each pixel in the image, have a high computational cost, particularly in the determination of the weights to assign to the neighboring pixel values. In addition, the efficiency of the interpolation operations decreases as the desired accuracy of the interpolation increases. As a result, the interpolation operations reduce the throughput of the graphics system and may be so time consuming as to be unacceptable to a user. What is needed, therefore, is a computer graphics system that efficiently performs the interpolation operations while not sacrificing the resulting accuracy.